/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	src/htable.c
 * @brief 
 *      Hashtable module, A basic datastruct module.
 *      Memory-free operations, generic frame of hash-table datastructs
 *      Thread-safe htable implementation
 *      -1. chaining htable
 *      -2. open-addressing htable
 *
 * @module      dlib
 * @see		dlib
 *
 * @history
 *	version 0.1.0, spark init htable module with chaining-htable 
 *	version 0.2.0, spark add open-addressing htable
 *	version 0.3.0, spark add simple chaining-htable module
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc.h"
#include "htable.h"

/** htable id for statics dump */
static uint32_t ht_id = 0;

/**
 * simple chaining-htable implementation
 * from YAEZ-server-framework by magic
 */

/**
 * _ht_naive_find
 * find a key in link list, use to find key in a bucket
 * @return 0 found, -1 not found
 * @param head link list head pointer
 * @param efunc equal function
 * @param key pointer to key field
 * @param prev previous item of found key
 * @param item pointer to found item
 */
static inline int _ht_naive_find(hnode_naive_t *head, ht_compare_fn c, void *key,
		hnode_naive_t **prev, hnode_naive_t **item)
{
	hnode_naive_t *curr = head;
	*prev = NULL;
	while (curr) {
		if ((*c)(curr->hn_key, key) != 0) {
			*prev = curr;
			curr = curr->hn_next;
		} else { /* find it */
			*item = curr;
			return 0;
		}
	}
	return -1;
}

htable_naive_t *ht_naive_init(dlib_alloc_t *na, int span,
		ht_hash_fn h, void *arg, ht_compare_fn c)
{
	size_t hash_map_size = HTABLE_NAIVE_SIZE(span);
	htable_naive_t *ht = (htable_naive_t *)dlib_naive_alloc(na, hash_map_size);
	if (ht != NULL) {
		memset(ht, 0, hash_map_size);

		ht->ht_bucket_size = span;
		ht->ht_na = na;
		ht->ht_hfunc = h;
		ht->ht_harg = arg;
		ht->ht_cfunc = c;
	}
	return ht;
}

int ht_naive_get(htable_naive_t *ht, void *key, long **val)
{
	uint32_t hval = (*ht->ht_hfunc)(key, ht->ht_harg);
	uint32_t bucket_index = hval % ht->ht_bucket_size;

	hnode_naive_t *pre;
	hnode_naive_t *curr;

	if (_ht_naive_find(ht->ht_buckets[bucket_index],
				ht->ht_cfunc, key, &pre, &curr) == 0) {
		*val = (long *)curr->hn_val;
		return 0;
	} 

	return -1;
}

int ht_naive_set(htable_naive_t *ht, void *key, void *val)
{
	uint32_t hval = (*ht->ht_hfunc)(key, ht->ht_harg);
	uint32_t bucket_index = hval % ht->ht_bucket_size;

	hnode_naive_t *pre;
	hnode_naive_t *curr;

	if (_ht_naive_find(ht->ht_buckets[bucket_index],
				ht->ht_cfunc, key, &pre, &curr) == 0) {
		curr->hn_val = val;
		return 0;
	}

	return ht_naive_insert(ht, key, val);
}
	

int ht_naive_insert(htable_naive_t *ht, void *key, void *val)
{
	uint32_t hval = (*ht->ht_hfunc)(key, ht->ht_harg);
	uint32_t bucket_index = hval % ht->ht_bucket_size;

	hnode_naive_t *pre;
	hnode_naive_t *curr;

	if (_ht_naive_find(ht->ht_buckets[bucket_index],
				ht->ht_cfunc, key, &pre, &curr) == 0) {
		return -1;
	}

	hnode_naive_t *item = (hnode_naive_t *)dlib_naive_alloc(ht->ht_na, sizeof(*item));

	if (item == NULL) {
		return -2;
	}

	item->hn_key = key;
	item->hn_val = val;
	if (ht->ht_buckets[bucket_index] != NULL) {
		item->hn_next = ht->ht_buckets[bucket_index];
	} else {
		item->hn_next = NULL;
	}
	ht->ht_buckets[bucket_index] = item;

	return 0;
}

int ht_naive_del(htable_naive_t *ht, void *key)
{
	uint32_t hval = (*ht->ht_hfunc)(key, ht->ht_harg);
	uint32_t bucket_index = hval % ht->ht_bucket_size;

	hnode_naive_t *pre;
	hnode_naive_t *curr;

	if (_ht_naive_find(ht->ht_buckets[bucket_index],
				ht->ht_cfunc, key, &pre, &curr) == 0) {
		if (pre == NULL) { /* curr is head */
			ht->ht_buckets[bucket_index] = NULL;
		} else {
			pre->hn_next = curr->hn_next;
		}
		return 0;
	} 
	return -1;
}


/** chaining-htable implemetation */
/**
 * _hn_init
 * @brief initialize htable node struct
 * @param table: htable struct
 */
static inline hnode_t *_hn_init(htable_t *table);

/**
 * _hn_exit
 * @brief destroy an htable node struct
 * @param hn: htable node struct
 * @param key_freed: free key for hnode by hand
 * @param r: the release value function, free value for hnode by hand
 */
static inline void _hn_exit(hnode_t *hn, uint16_t key_freed, ht_relval_fn r);

/**
 * _ht_lookup
 * @brief lookup an htable node in htable buckets
 * @param table: htable struct
 * @param k: key of node
 * @param h: hash value of key
 */
static inline hnode_t *_ht_lookup(htable_t *table, const void *k, uint32_t h);

#ifdef _DEBUG
/**
 * _ht_statics_init
 * @brief initialize htable statics struct
 * @param table: htable struct
 */

static inline htstatics_t *_ht_statics_init(htable_t *table);

/**
 * _ht_statics_exit
 * @brief destructure of htable statics struct
 * @param statics: htable statics struct
 */
static inline void _ht_statics_exit(htstatics_t *statics);

static htstatics_t *_ht_statics_init(htable_t *table)
{
	htstatics_t *statics = NULL;
	
#ifdef _DLIB_HTABLE_USE_MARENA
	statics = dlib_marena_calloc(table->ht_p, sizeof (htstatics_t));
	statics->hs_buckets_num = 
		dlib_marena_calloc(table->ht_p, table->ht_span * sizeof (uint32_t));
#else
	statics = (htstatics_t *)dmalloc(sizeof (htstatics_t));
	statics->hs_buckets_num = dmalloc(table->ht_span * sizeof (uint32_t));
#endif
	dlib_lock_init(&statics->hs_lock);
	
	return statics;
}

static void _ht_statics_exit(htstatics_t *statics)
{
	dlib_lock_exit(&statics->hs_lock);
#ifndef _DLIB_HTABLE_USE_MARENA
	dfree(statics->hs_buckets_num);
	dfree(statics);
	statics = NULL;
#endif
	return;
}
#endif

static inline hnode_t *_hn_init(htable_t *table)
{
	hnode_t *hn = NULL;
#ifdef _DLIB_HTABLE_USE_MARENA
	hn = dlib_marena_calloc(table->ht_p, sizeof (hnode_t));
#else
	UNUSED_PARAM(table);
	hn = (hnode_t *)dmalloc(sizeof (hnode_t));
#endif
	dlib_lock_init(&hn->hn_lock);
	
	return hn;
}

static inline void _hn_exit(hnode_t *hn, uint16_t key_freed, ht_relval_fn r)
{
	if (hn == NULL) return;
	
	dlib_lock_exit(&hn->hn_lock);
	
	if (key_freed != 0)
		dfree(hn->key);
	if (r != NULL) {
		if (hn->val != NULL)
			(*r)(hn->val);
	}
#ifndef _DLIB_HTABLE_USE_MARENA
	dfree(hn);
	hn = NULL;
#endif
	return;
}

static inline hnode_t *_ht_lookup(htable_t *table, const void *k, uint32_t h)
{
	hnode_t *tpos = NULL;
	hlist_node_t *pos;

	dlib_lock_lock(table->b_locks + h);
	HLIST_FOREACH_ENTRY(tpos, pos, table->buckets + h, hl) {
		dlib_lock_lock(&tpos->hn_lock);
		if (tpos != NULL && tpos->key != NULL &&
		    table->ht_compare != NULL && 
		    (*table->ht_compare)(k, tpos->key) == 0) {
			/** lock the node first when find it */
			dlib_lock_unlock(table->b_locks + h);
			return tpos;
		}
		dlib_lock_unlock(&tpos->hn_lock);
	}
	dlib_lock_unlock(table->b_locks + h);
	
	return NULL;
}

htable_t *ht_init(uint32_t span, ht_hash_fn h, void *arg, ht_compare_fn c,
		  uint16_t key_freed, ht_relval_fn r)
{
	uint32_t i;
	htable_t *table = NULL;
	
	if (span == 0 || h == NULL || c == NULL)
		return NULL;

	span = near_primer(span);

#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_t *p = NULL;
	uint32_t p_original_size = 0;	/* marena original size */
	
	p_original_size = sizeof (htable_t) + span * 
			  (sizeof (dlib_lock_t) + sizeof (hlist_head_t));
	
	p = dlib_marena_new_with_heap(p_original_size);
	table = dlib_marena_calloc(p, sizeof (*table));
	
	table->ht_p = p;
	
	table->buckets = dlib_marena_calloc(p, span * sizeof (hlist_head_t));
	table->b_locks = dlib_marena_calloc(p, span * sizeof (dlib_lock_t));
#else
	table = (htable_t *)dmalloc(sizeof (*table));
	
	table->buckets = (hlist_head_t *)dmalloc(span * sizeof (hlist_head_t));
	table->b_locks = dmalloc(span * sizeof (dlib_lock_t));
#endif
	
	table->ht_key_freed = key_freed;
	table->ht_rel_val = r;
	
	table->ht_id = ht_id++;
	table->ht_span = span;
	table->ht_count = 0;

	table->iter_bucket = 0;
	table->iter_node = NULL;
	
	table->ht_hash = h;
	table->ht_hash_arg = arg;
	table->ht_compare = c;

	dlib_lock_init(&table->ht_lock);
	for (i = 0; i < span; i++) {
		dlib_lock_init(table->b_locks + i);
	}
	
#ifdef _DEBUG
	table->ht_statics = _ht_statics_init(table);
#endif
	
	return table;
}

void ht_exit(htable_t *table)
{
	uint32_t i;
	
	hnode_t *tpos = NULL;
	hlist_node_t *pos = NULL;
	hlist_node_t *n = NULL;
	
	if (table == NULL) return;
	
	dlib_lock_lock(&table->ht_lock);
#ifdef _DEBUG
	_ht_statics_exit(table->ht_statics);
#endif
	for (i = 0; i < table->ht_span; i++) {
		dlib_lock_lock(table->b_locks + i);
		HLIST_FOREACH_ENTRY_SAFE(tpos, pos, n, table->buckets + i, hl) {
			_hn_exit(tpos, table->ht_key_freed, table->ht_rel_val);
		}
		dlib_lock_unlock(table->b_locks + i);
		dlib_lock_exit(table->b_locks + i);
	}
	dlib_lock_unlock(&table->ht_lock);
	dlib_lock_exit(&table->ht_lock);
	
#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_free(table->ht_p);
#else
	dfree(table->buckets);
	dfree(table->b_locks);
	dfree(table);
	table = NULL;
#endif

	return;
}

int ht_set(htable_t *table, void *k, void *v)
{
	hnode_t *n = NULL;
	uint32_t h = 0;

	if (table == NULL || k == NULL || v == NULL)
		return -1;
	if (table->ht_hash == NULL)
		return -10;

	h = (*table->ht_hash)(k, table->ht_hash_arg) % table->ht_span;
	/* when return a node, it locked the node */
	n = _ht_lookup(table, k, h);
	
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_sets++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif

	/* not allow to set duplicate keys */
	if (n != NULL) {
		//dlib_lock_lock(&n->hn_lock);
		if (table->ht_key_freed != 0)
			dfree(n->key);
		if (table->ht_rel_val != NULL)
			if (n->val != NULL)
				(*table->ht_rel_val)(n->val);
		n->key = k;
		n->val = v;
		dlib_lock_unlock(&n->hn_lock);
		
		return 0;
	}

	n = _hn_init(table);
	
	n->key = k;
	n->val = v;

	dlib_lock_lock(table->b_locks + h);
	HLIST_ADD(table->buckets + h, &n->hl);
	dlib_lock_unlock(table->b_locks + h);
	
	dlib_lock_lock(&table->ht_lock);
	table->ht_count++;
	dlib_lock_unlock(&table->ht_lock);

#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	(table->ht_statics->hs_buckets_num)[h]++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
	return 0;
}

void *ht_get(htable_t *table, const void *k)
{
	hnode_t *n = NULL;
	uint32_t h = 0;

	if (table == NULL || k == NULL)
		return NULL;

	h = (*table->ht_hash)(k, table->ht_hash_arg) % table->ht_span;
	/* when return a node, it locked the node */
	n = _ht_lookup(table, k, h);
	
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_gets++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif

	if (n == NULL) {
		return NULL;
	}
	dlib_lock_unlock(&n->hn_lock);
	return n->val;
}

int ht_del(htable_t *table, const void *k)
{
	hnode_t *n = NULL;
	uint32_t h = 0;

	if (table == NULL || k == NULL)
		return -1;

	h = (*table->ht_hash)(k, table->ht_hash_arg) % table->ht_span;
	/* when return a node, it locked the node */
	n = _ht_lookup(table, k, h);
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_dels++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
	if (n == NULL) {
		return -10;
	}

	dlib_lock_lock(table->b_locks + h);
	HLIST_DEL(&n->hl);
	dlib_lock_unlock(&n->hn_lock);
	dlib_lock_unlock(table->b_locks + h);
	
	dlib_lock_lock(&table->ht_lock);
	table->ht_count--;
	dlib_lock_unlock(&table->ht_lock);
	
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	(table->ht_statics->hs_buckets_num)[h]--;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
	_hn_exit(n, table->ht_key_freed, table->ht_rel_val);

	return 0;
}

int ht_walker_from(htable_t *table, const void *k)
{
	hnode_t *n = NULL;
	uint32_t h = 0;
	
	if (table == NULL)
		return -1;
	
	if (k == NULL) {
		table->iter_bucket = 0;
		table->iter_node = NULL;
		return 0;
	}
	
	h = (*table->ht_hash)(k, table->ht_hash_arg) % table->ht_span;
	n = _ht_lookup(table, k, h);
	if (n == NULL) return 0;

	dlib_lock_lock(&table->ht_lock);
	table->iter_bucket = h;
	table->iter_node = n;
	dlib_lock_unlock(&n->hn_lock);
	dlib_lock_unlock(&table->ht_lock);

	return 0;
}

int ht_walker(htable_t *table, ht_walker_fn w, void *arg)
{
	uint32_t i;
	hnode_t *tpos = NULL;
	hnode_t *temp = NULL;
	hlist_node_t *pos = NULL;
	hlist_node_t *n = NULL;

	if (table == NULL || w == NULL)
		return -1;

	/* check from-node is set, walker from from-node */
	dlib_lock_lock(&table->ht_lock);
	temp = table->iter_node;
	if (temp == NULL) {
		i = table->iter_bucket;
	} else {
		i = table->iter_bucket + 1; 
	}
	dlib_lock_unlock(&table->ht_lock);

	if (temp == NULL) {
		for (; i < table->ht_span; i++) {
			dlib_lock_lock(table->b_locks + i);
			HLIST_FOREACH_ENTRY_SAFE(tpos, pos, n,
						 table->buckets + i, hl) {
				if (tpos != NULL)
					(*w)(tpos->key, tpos->val, arg);
			}
			dlib_lock_unlock(table->b_locks + i);
		}
	} else {
		dlib_lock_lock(table->b_locks + i - 1);
		pos = &temp->hl;
		HLIST_FOREACH_ENTRY_SAFE_FROM(tpos, pos, n, hl) {
			if (tpos != NULL)
				(*w)(tpos->key, tpos->val, arg);
		}
		dlib_lock_unlock(table->b_locks + i - 1);
		tpos = NULL;
		for (; i < table->ht_span; i++) {
			dlib_lock_lock(table->b_locks + i);
			HLIST_FOREACH_ENTRY_SAFE(tpos, pos, n,
						 table->buckets + i, hl) {
				if (tpos != NULL)
					(*w)(tpos->key, tpos->val, arg);
			}
			dlib_lock_unlock(table->b_locks + i);
		}
	}

	return 0;
}

void ht_dump(htable_t *table)
{
	if (table == NULL) return;

	dlib_lock_lock(&table->ht_lock);
	fprintf(stdout, "HTABLE(%d) dump out:\n", table->ht_id);
	fprintf(stdout, "    span is %d.\n", table->ht_span);
	fprintf(stdout, "    count is %d.\n", table->ht_count);
#ifdef _DLIB_HTABLE_USE_MARENA
	if (table->ht_p != NULL)
		fprintf(stdout, "    marena is %p.\n", table->ht_p);
	else
		fprintf(stdout, "    marena is NULL.\n");
#endif
	fprintf(stdout, "    key_freed is %d.\n", table->ht_key_freed);
	if (table->ht_rel_val != NULL)
		fprintf(stdout, "    release_fn is %p.\n", table->ht_rel_val);
	else
		fprintf(stdout, "    release_fn is NULL.\n");
	dlib_lock_unlock(&table->ht_lock);

#ifdef _DEBUG
	uint32_t i;
	dlib_lock_lock(&table->ht_statics->hs_lock);
	fprintf(stdout, "\n");
	fprintf(stdout, "    htable set number is %d.\n",
		table->ht_statics->hs_sets);
	fprintf(stdout, "    htable get number is %d.\n",
		table->ht_statics->hs_gets);
	fprintf(stdout, "    htable del number is %d.\n",
		table->ht_statics->hs_dels);
	fprintf(stdout, "\n");
	for (i = 0; i < table->ht_span; i++) {
		fprintf(stdout, "    bucket[%u] len %d.\n", i,
			(table->ht_statics->hs_buckets_num)[i]);
	}
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
	return;
}

/** open-addressing htable implemetation */
/** mark delete flag */
static hnode_open_t _hnode_open_deleted = {
	NULL,
	NULL,
};

/**
 * _hn_open_init
 * @brief initialize htable node struct
 * @param table: htable struct
 */
static inline hnode_open_t *_hn_open_init(htable_open_t *table);

/**
 * _hn_open_exit
 * @brief destroy an htable node struct
 * @param hn: htable node struct
 * @param key_freed: free key for hnode by hand
 * @param r: the release value function, free value for hnode by hand
 */
static inline void _hn_open_exit(hnode_open_t *hn, uint16_t key_freed,
				 ht_relval_fn r);

/**
 * _ht_open_set
 * @brief set k-v to table with no lock
 * @param table: htable 
 * @param k: key
 * @param v: value
 */
static int _ht_open_set(htable_open_t *table, void *k, void *v);

#ifdef _DEBUG
/**
 * _ht_open_statics_init
 * @brief initialize htable statics struct
 * @param table: htable struct
 */
static inline htstatics_open_t *_ht_open_statics_init(htable_open_t *table);

/**
 * _ht_open_statics_exit
 * @brief destructure of htable statics struct
 * @param statics: htable statics struct
 */
static inline void _ht_open_statics_exit(htstatics_open_t *statics);

static htstatics_open_t *_ht_open_statics_init(htable_open_t *table)
{
	htstatics_open_t *statics = NULL;
	
#ifdef _DLIB_HTABLE_USE_MARENA
	statics = dlib_marena_calloc(table->ht_p, sizeof (htstatics_open_t));
#else
	UNUSED_PARAM(table);
	statics = (htstatics_open_t *)dmalloc(sizeof (htstatics_open_t));
#endif
	dlib_lock_init(&statics->hs_lock);
	
	return statics;
}

static void _ht_open_statics_exit(htstatics_open_t *statics)
{
	dlib_lock_exit(&statics->hs_lock);
#ifndef _DLIB_HTABLE_USE_MARENA
	dfree(statics);
	statics = NULL;
#endif
	return;
}
#endif

static inline hnode_open_t *_hn_open_init(htable_open_t *table)
{
	hnode_open_t *hn = NULL;
#ifdef _DLIB_HTABLE_USE_MARENA
	hn = dlib_marena_calloc(table->ht_p, sizeof (hnode_open_t));
#else
	UNUSED_PARAM(table);
	hn = (hnode_open_t *)dmalloc(sizeof (hnode_open_t));
#endif
	
	return hn;
}

static inline void _hn_open_exit(hnode_open_t *hn, uint16_t key_freed,
				 ht_relval_fn r)
{
	if (hn == NULL) return;
	
	if (key_freed != 0)
		dfree(hn->key);
	if (r != NULL && hn != &_hnode_open_deleted) {
		if (hn->val != NULL)
			(*r)(hn->val);
	}
#ifndef _DLIB_HTABLE_USE_MARENA
	if (hn != NULL && hn != &_hnode_open_deleted) {
		dfree(hn);
		hn = NULL;
	}
#endif
	return;
}

static int _ht_open_set(htable_open_t *table, void *k, void *v)
{
	int ret = -1;
	uint32_t i = 0;
	hnode_open_t **n = NULL;
	uint32_t h, h1, h2;

	/* find a node to set */
	for (i = 0; i < table->ht_span; i++) {
		h1 = h2 = 0;
		h = (*table->ht_hash)(k, table->ht_hash_arg);
		h1 = h % table->ht_span;
		if (i != 0)
			h2 = 1 + h % (table->ht_span - 1);
		h = (h1 + i * h2) % table->ht_span;
		/* find a node to use */
		if (table->buckets[h] == NULL ||
		    table->buckets[h] == &_hnode_open_deleted) {
			n = &table->buckets[h];
			break;
		} else {
			if ((*table->ht_compare)
			    (k, table->buckets[h]->key) == 0) {
				n = &table->buckets[h];
				break;
			}
#ifdef _DEBUG
			dlib_lock_lock(&table->ht_statics->hs_lock);
			table->ht_statics->hs_collisions++;
			dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
		}
	}
	
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_sets++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif

	/* not allow to set duplicate keys */
	if (n != NULL) {
		if (*n == NULL || *n == &_hnode_open_deleted) {
			hnode_open_t *o = _hn_open_init(table);
			o->key = k;
			o->val = v;
			*n = o;
			table->ht_count++;
			ret = 0;
		} else {
			hnode_open_t *o = *n;
			if (table->ht_key_freed != 0)
				dfree(o->key);
			if (table->ht_rel_val != NULL)
				if (o->val != NULL)
					(*table->ht_rel_val)(o->val);
			o->key = k;
			o->val = v;
			ret = 0;
		}
	}

	return ret;
}

htable_open_t *ht_open_init(uint32_t span, ht_hash_fn h, void *arg,
			    ht_compare_fn c, uint16_t key_freed,
			    ht_relval_fn r)
{
	htable_open_t *table = NULL;
	
	if (span == 0 || h == NULL || c == NULL)
		return NULL;

	span = near_primer(span);

#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_t *p = NULL;
	uint32_t p_original_size = 0;	/* marena original size */
	
	p_original_size = sizeof (htable_open_t) + span * 
			  (sizeof (hnode_open_t *) + sizeof (hnode_open_t));
	
	p = dlib_marena_new_with_heap(p_original_size);
	table = dlib_marena_calloc(p, sizeof (*table));
	
	table->ht_p = p;
	
	table->buckets = dlib_marena_calloc(p, span * sizeof (hnode_open_t *));
#else
	table = (htable_open_t *)dmalloc(sizeof (*table));
	table->buckets = (hnode_open_t **)dmalloc(span * sizeof (hnode_open_t *));
#endif
	
	table->ht_key_freed = key_freed;
	table->ht_rel_val = r;
	
	table->ht_id = ht_id++;
	table->ht_span = span;
	table->ht_count = 0;

	table->ht_hash = h;
	table->ht_hash_arg = arg;
	table->ht_compare = c;

	dlib_lock_init(&table->ht_lock);

#ifdef _DEBUG
	table->ht_statics = _ht_open_statics_init(table);
#endif
	return table;
}

void ht_open_exit(htable_open_t *table)
{
	uint32_t i;
	if (table == NULL) return;
	
	dlib_lock_lock(&table->ht_lock);
#ifdef _DEBUG
	_ht_open_statics_exit(table->ht_statics);
#endif
	for (i = 0; i < table->ht_span; i++) {
		_hn_open_exit(table->buckets[i], table->ht_key_freed,
			      table->ht_rel_val);
	}
	dlib_lock_unlock(&table->ht_lock);
	dlib_lock_exit(&table->ht_lock);
	
#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_free(table->ht_p);
#else
	dfree(table->buckets);
	dfree(table);
	table = NULL;
#endif
	return;
}

int ht_open_set(htable_open_t *table, void *k, void *v)
{
	int ret = -1;

	if (table == NULL || k == NULL || v == NULL)
		return -2;
	if (table->ht_hash == NULL)
		return -3;

	dlib_lock_lock(&table->ht_lock);
	ret = _ht_open_set(table, k, v);
	dlib_lock_unlock(&table->ht_lock);

	return ret;
}

void *ht_open_get(htable_open_t *table, const void *k)
{
	uint32_t i = 0;
	hnode_open_t **n = NULL;
	uint32_t h, h1, h2;

	if (table == NULL || k == NULL)
		return NULL;

	/* find a node */
	dlib_lock_lock(&table->ht_lock);
	for (i = 0; i < table->ht_span; i++) {
		h1 = h2 = 0;
		h = (*table->ht_hash)(k, table->ht_hash_arg);
		h1 = h % table->ht_span;
		if (i != 0)
			h2 = 1 + h % (table->ht_span - 1);
		h = (h1 + i * h2) % table->ht_span;
		if (table->buckets[h] == NULL) {
			n = NULL; 
			break;
		} else {
			if (table->buckets[h] == &_hnode_open_deleted) {
				continue;
			}
			if ((*table->ht_compare)
			    (k, table->buckets[h]->key) == 0) {
				n = &table->buckets[h];
				break;
			}
#ifdef _DEBUG
			dlib_lock_lock(&table->ht_statics->hs_lock);
			table->ht_statics->hs_collisions++;
			dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
		}
	}
	
#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_gets++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif

	dlib_lock_unlock(&table->ht_lock);
	if (n == NULL) {
		return NULL;
	}

	return (*n)->val;
}

int ht_open_del(htable_open_t *table, const void *k)
{
	uint32_t i = 0;
	hnode_open_t **n = NULL;
	hnode_open_t *o = NULL;
	uint32_t h, h1, h2;

	if (table == NULL || k == NULL)
		return -1;

	/* find a node to del */
	dlib_lock_lock(&table->ht_lock);
	for (i = 0; i < table->ht_span; i++) {
		h1 = h2 = 0;
		h = (*table->ht_hash)(k, table->ht_hash_arg);
		h1 = h % table->ht_span;
		if (i != 0)
			h2 = 1 + h % (table->ht_span - 1);
		h = (h1 + i * h2) % table->ht_span;
		if (table->buckets[h] == NULL) {
			n = NULL; 
			break;
		} else {
			if (table->buckets[h] == &_hnode_open_deleted) {
				continue;
			}
			if ((*table->ht_compare)
			    (k, table->buckets[h]->key) == 0) {
				n = &table->buckets[h];
				break;
			}
#ifdef _DEBUG
			dlib_lock_lock(&table->ht_statics->hs_lock);
			table->ht_statics->hs_collisions++;
			dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
		}
	}

#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	table->ht_statics->hs_dels++;
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif

	if (n == NULL) {
		dlib_lock_unlock(&table->ht_lock);
		return -10;
	}

	o = *n;
	*n = &_hnode_open_deleted;
	table->ht_count--;
	dlib_lock_unlock(&table->ht_lock);
	
	_hn_open_exit(o, table->ht_key_freed, table->ht_rel_val);

	return 0;
}

int ht_open_walker(htable_open_t *table, ht_walker_fn w, void *arg)
{
	uint32_t i;

	if (table == NULL || w == NULL)
		return -1;

	dlib_lock_lock(&table->ht_lock);
	for (i = 0; i < table->ht_span; i++) {
		if (table->buckets[i] != NULL &&
		    table->buckets[i] != &_hnode_open_deleted) {
			(*w)(table->buckets[i]->key,
			     table->buckets[i]->val, arg);
		}
	}
	dlib_lock_unlock(&table->ht_lock);

	return 0;
}

int ht_open_expand(htable_open_t *table, uint32_t span)
{
	uint32_t i;

	if (table == NULL)
		return -1;
	span = near_primer(span);
	if (span <= table->ht_span)
		return -2;

	dlib_lock_lock(&table->ht_lock);
#ifdef _DLIB_HTABLE_USE_MARENA
	hnode_open_t **temp = NULL;
	temp = table->buckets;
	table->buckets = dlib_marena_calloc(table->ht_p,
			span * sizeof (hnode_open_t *));
	memcpy(table->buckets, temp, table->ht_span * sizeof (hnode_open_t *));
#else
	/* be sure realloc will be success */
	table->buckets = (hnode_open_t **)drealloc(table->buckets,
			span * sizeof (hnode_open_t *));
#endif
	for (i = table->ht_span; i < span; i++)
		table->buckets[i] = &_hnode_open_deleted;
	table->ht_span = span;
	dlib_lock_unlock(&table->ht_lock);
	
	return 0;
}

int ht_open_rehash(htable_open_t *table)
{
	uint32_t i;
	int ret = 0;
	void *key, *val;
	if (table == NULL)
		return -1;

	dlib_lock_lock(&table->ht_lock);
	for (i = 0; i < table->ht_span; i++) {
		if (table->buckets[i] != NULL &&
		    table->buckets[i] != &_hnode_open_deleted) {
			key = table->buckets[i]->key;
			val = table->buckets[i]->val;
			table->buckets[i] = &_hnode_open_deleted;
			ret = _ht_open_set(table, key, val);
			if (ret < 0) {
				table->buckets[i]->key = key;
				table->buckets[i]->val = val;
			}
		}
	}
	dlib_lock_unlock(&table->ht_lock);

	return 0;
}

void ht_open_dump(htable_open_t *table)
{
	if (table == NULL) return;

	dlib_lock_lock(&table->ht_lock);
	fprintf(stdout, "HTABLE open-addressing(%d) dump out:\n",
		table->ht_id);
	fprintf(stdout, "    span is %d.\n", table->ht_span);
	fprintf(stdout, "    count is %d.\n", table->ht_count);
#ifdef _DLIB_HTABLE_USE_MARENA
	if (table->ht_p != NULL)
		fprintf(stdout, "    marena is %p.\n", table->ht_p);
	else
		fprintf(stdout, "    marena is NULL.\n");
#endif
	fprintf(stdout, "    key_freed is %d.\n", table->ht_key_freed);
	if (table->ht_rel_val != NULL)
		fprintf(stdout, "    release_fn is %p.\n", table->ht_rel_val);
	else
		fprintf(stdout, "    release_fn is NULL.\n");
	dlib_lock_unlock(&table->ht_lock);

#ifdef _DEBUG
	dlib_lock_lock(&table->ht_statics->hs_lock);
	fprintf(stdout, "\n");
	fprintf(stdout, "    htable set number is %d.\n",
		table->ht_statics->hs_sets);
	fprintf(stdout, "    htable get number is %d.\n",
		table->ht_statics->hs_gets);
	fprintf(stdout, "    htable del number is %d.\n",
		table->ht_statics->hs_dels);
	fprintf(stdout, "    htable collision number is %d.\n",
		table->ht_statics->hs_collisions);
	dlib_lock_unlock(&table->ht_statics->hs_lock);
#endif
	return;
}
